"""
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

105. 从前序与中序遍历序列构造二叉树
已解答
中等
相关标签
premium lock icon
相关企业
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

 

示例 1:


输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]
 

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列

"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import List, Optional
from tree_node import TreeNode,build_tree_node


class Solution:
    """
    首先梳理下两种顺序遍历的核心：
    前序遍历：中-前-后
    中序遍历：前-中-后

    3   9   20  15  7
    9   3   15  20  7

    核心是将数组分为3部分。再逐次分下去。
    拿到前序遍历数组，确定第1个元素是根节点，余下的部分再拆分为左子树和右子树的遍历。
    拿到中序遍历数组，利用节点无重复元素的特性，确定根节点所在索引，将之拆分。数组左边是左子树，数组右边是右子树。
    拿到中序遍历的左子树和右子树后，根据右子树的数量可以从前序遍历数组中推测出前序遍历对应的左子树和右子树，之后在继续推进即可

    
    """
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None

        root=TreeNode(preorder[0])
        root_in_idx=inorder.index(root.val)
        left_preorder=preorder[1:root_in_idx+1]
        right_preorder=preorder[root_in_idx+1:]
        left_inorder=inorder[:root_in_idx]
        right_inorder=inorder[root_in_idx+1:]

        left_node=self.buildTree(left_preorder,left_inorder)
        right_node=self.buildTree(right_preorder,right_inorder)
        root.left=left_node
        root.right=right_node
        
        return root
    
if __name__=='__main__':
    preorder=[3,9,20,15,7]
    inorder=[9,3,15,20,7]

    s=Solution()
    res=s.buildTree(preorder,inorder)
    l=res.preorder_traversal()
    print(l)